package com.wtgroup.demo.mianshi.算法.etc;

import cn.hutool.core.collection.CollUtil;
import cn.hutool.core.util.StrUtil;
import com.wtgroup.demo.common.judge.Judger;
import lombok.AllArgsConstructor;
import lombok.EqualsAndHashCode;
import lombok.NoArgsConstructor;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/6 17:06
 */
public class D_递归改迭代_汉诺塔 {
    public static void main(String[] args) {
        Judger.of(() -> {

            ArrayList<Aciton> res1 = S1.func(5, "L", "R", "M");
            ArrayList<Aciton> res2 = S2.loop(5, "L", "R", "M");

            // 对比 结果1 和 结果2
            boolean ret = CollUtil.isEqualList(res1, res2);
            if (!ret) {
                System.out.println(res1);
                System.out.println(res2);
            }


            return ret;
        }).setIterCount(1000).start().print();
    }

    @NoArgsConstructor
    @AllArgsConstructor
    @EqualsAndHashCode
    static class Aciton {
        int i;
        String from;
        String to;

        @Override
        public String toString() {
            // return i + "," + from + "," + to;
            return StrUtil.format("{}-{}-{}", from, i, to);
        }
    }

    static class S1 {

        // public static void hanoi(int n) {
        //     if (n > 0) {
        //         func(n, "left", "right", "mid");
        //     }
        // }

        public static ArrayList<Aciton> func(int N, String from, String to, String other) {
            ArrayList<Aciton> actions = new ArrayList<>();
            // 异常数据处理
            if (N <= 0) {
                return actions;
            }

            if (N == 1) { // base
                // System.out.println("Move 1 from " + from + " to " + to);
                actions.add(new Aciton(1, from, to));
            } else {
                ArrayList<Aciton> acitons1 = func(N - 1, from, other, to);
                actions.addAll(acitons1);
                // System.out.println("Move " + N + " from " + from + " to " + to);
                actions.add(new Aciton(N, from, to));
                ArrayList<Aciton> acitons2 = func(N - 1, other, to, from);
                actions.addAll(acitons2);
            }

            return actions;
        }
    }

    @AllArgsConstructor
    static class Frame {
        int N;
        String from;
        String to;
        String other;
    }

    static class S2 {

        static ArrayList<Aciton> loop(int _N, String _from, String _to, String _other) {
            ArrayList<Aciton> actions = new ArrayList<>();

            // 异常数据处理
            if (_N <= 0) {
                return actions;
            }

            Stack<Frame> stack = new Stack<>();
            stack.push(new Frame(_N, _from, _to, _other));
            Map<Frame, Integer> frameToOffsetMap = new HashMap<>();

            while (!stack.isEmpty()) {
                Frame currFrame = stack.pop();
                // 1. base case , continue -- 递归的退出条件
                // if xxx:
                //  continue
                if (currFrame.N == 1) {
                    // System.out.println("Move 1 from" + from + " to " + to);
                    actions.add(new Aciton(1, currFrame.from, currFrame.to));
                    continue;
                }
                // --- ↑ continue -- 递归的退出条件 ---

                Integer currHandlePoint = frameToOffsetMap.getOrDefault(currFrame, -1) + 1;
                // 2. 择机调用处理器逻辑
                // 当前处理分支 和 指定调用的时机比较
                // if (currHandlePoint == (childCnt+1) / 2) {
                //     System.out.print(node.getData() + " ");
                // }
                // 如果左节点处理过了, 说明, 该处理我自身
                if (currHandlePoint == 1) {
                    // System.out.println("Move " + N + " from " + from + " to " + to);
                    actions.add(new Aciton(currFrame.N, currFrame.from, currFrame.to));
                }

                // 3. 当前节点的子分支处理完了, continue
                // if frameOffsetMap.get(currFrame) == nexts.size
                //   continue


                if (currHandlePoint == 2) {
                    continue;
                }


                // 4. 否则, 自己压回栈中, 封装子节点处 Frame 压栈, 进入下一个子节点处处理. 并更新当前节点的子分支偏移量
                stack.push(currFrame);
                Frame toPushFrame = null;
                if (currHandlePoint == 0) {
                    toPushFrame = new Frame(currFrame.N - 1, currFrame.from, currFrame.other, currFrame.to);
                } else {
                    toPushFrame = new Frame(currFrame.N - 1, currFrame.other, currFrame.to, currFrame.from);
                }
                stack.push(toPushFrame);
                frameToOffsetMap.put(currFrame, currHandlePoint);
            }

            return actions;
        }


    }


}
